//
// Created by Administrator on 2021/7/3.
//
#include <vector>
#include <iostream>
#include <queue>

using namespace std;

class Solution {
private:
    const vector<pair<int, int>> neighbor{{-1, -1},
                                          {-1, 0},
                                          {-1, 1},
                                          {0,  -1},
                                          {0,  1},
                                          {1,  -1},
                                          {1,  0},
                                          {1,  1}};
public:
    vector<vector<char>> updateBoard(vector<vector<char>> &board, vector<int> &click) {
        //做出一个雷区矩阵,表明当前位置四周八个位置有几个地雷
        unsigned int m = board.size(), n = board[0].size();
        vector<vector<int>> mineMap(m, vector<int>(n, 0));
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                // 遇到一个地雷,周围的八个格子都+1
                if (board[i][j] == 'M') {
                    // 地雷标记为-1
                    mineMap[i][j] = -1;
                    for (int k = 0; k < 8; ++k) {
                        auto newI = i + neighbor[k].first;
                        auto newJ = j + neighbor[k].second;
                        if (newI >= 0 and newI < m and newJ >= 0 and newJ < n and mineMap[newI][newJ] >= 0) {
                            ++mineMap[newI][newJ];
                        }
                    }
                }
            }
        }
        int clickX = click[0], clickY = click[1];
        // 如果一个地雷（'M'）被挖出，游戏就结束了- 把它改为 'X'。
        if (mineMap[clickX][clickY] == -1) {
            board[clickX][clickY] = 'X';
            return board;
        }
        // 如果一个至少与一个地雷相邻的空方块（'E'）被挖出，修改它为数字（'1'到'8'），表示相邻地雷的数量。
        if (mineMap[clickX][clickY] > 0) {
            board[clickX][clickY] = char(mineMap[clickX][clickY] + '0');
            return board;
        }
        // 如果一个没有相邻地雷的空方块（'E'）被挖出，修改它为（'B'），并且所有和其相邻的未挖出方块都应该被递归地揭露。
        // 通过bfs实现
        // 不断搜索周围的空白位(0)和相邻地雷位(>0)
        // 遇到0 则将其放入队列,board修改为'B'
        // 遇到>0 则不放入队列,显示出对应附近的地雷数量
        // 探索过的位置标记为9 (不可能周围有9个地雷)
        queue<pair<int, int>> q;
        q.emplace(clickX, clickY);
        while (!q.empty()) {
            auto p = q.front();
            q.pop();
            mineMap[p.first][p.second] = 9;
            board[p.first][p.second] = 'B';
            for (int k = 0; k < 8; ++k) {
                auto newX = p.first + neighbor[k].first;
                auto newY = p.second + neighbor[k].second;
                if (newX >= 0 and newX < m and newY >= 0 and newY < n and mineMap[newX][newY] >= 0) {
                    // 探索过
                    if (mineMap[newX][newY] == 9) continue;
                        // 空白位
                    else if (mineMap[newX][newY] == 0) q.emplace(newX, newY);
                        // 周围有地雷的位
                    else {
                        board[newX][newY] = char(mineMap[newX][newY] + '0');
                        mineMap[newX][newY] = 9;
                    }
                }
            }
        }
        return board;
        // 超时 28/54
    }
};

class Solution2 {
private:
    const vector<pair<int, int>> neighbor{{-1, -1},
                                          {-1, 0},
                                          {-1, 1},
                                          {0,  -1},
                                          {0,  1},
                                          {1,  -1},
                                          {1,  0},
                                          {1,  1}};
public:
    vector<vector<char>> updateBoard(vector<vector<char>> &board, vector<int> &click) {
        // 不探索地雷分布矩阵,直接判断
        int clickX = click[0], clickY = click[1];
        // 挖到雷
        if (board[clickX][clickY] == 'M') {
            board[clickX][clickY] = 'X';
            return board;
        }
        // 挖到相邻雷的空白位
        int initMineNum = countMine(board, clickX, clickY);
        if (initMineNum > 0) {
            board[clickX][clickY] = char('0' + initMineNum);
            return board;
        }
        // 挖到没雷的空白位
        queue<pair<int, int>> q;
        q.emplace(clickX, clickY);
        while (!q.empty()) {
            auto p = q.front();
            q.pop();
            board[p.first][p.second] = 'B';
            for (int k = 0; k < 8; ++k) {
                auto newX = p.first + neighbor[k].first;
                auto newY = p.second + neighbor[k].second;
                if (newX >= 0 and newX < board.size() and newY >= 0 and newY < board[0].size()) {
                    if (board[newX][newY] == 'M' or board[newX][newY] == 'B') continue;
                    // 在这里算了太多步
                    int localMineNum = countMine(board, newX, newY);
                    if (localMineNum == 0) q.emplace(newX, newY);
                    else {
                        board[newX][newY] = char(localMineNum + '0');
                    }
                }
            }
        }
        return board;
        // 依旧超时 28/54
    }

    /**
     * 判断board上[i,j]位置的四周有多少雷
     */
    int countMine(vector<vector<char>> &board, int i, int j) {
        int countAns = 0;
        for (int k = 0; k < 8; ++k) {
            int newX = neighbor[k].first + i;
            int newY = neighbor[k].second + j;
            if (newX >= 0 and newX < board.size() and newY >= 0 and newY < board[0].size()) {
                if (board[newX][newY] == 'M') ++countAns;
            }
        }
        return countAns;
    }
};

class Solution3 { // 题解bfs
public:
    int dir_x[8] = {0, 1, 0, -1, 1, 1, -1, -1};
    int dir_y[8] = {1, 0, -1, 0, 1, -1, 1, -1};

    void bfs(vector<vector<char>> &board, int sx, int sy) {
        // bfs队列
        queue<pair<int, int>> Q;
        // 记录搜索的二维数组
        vector<vector<bool>> vis(board.size(), vector<bool>(board[0].size(), false));
        Q.push({sx, sy});
        vis[sx][sy] = true;
        while (!Q.empty()) {
            auto pos = Q.front();
            Q.pop();
            int cnt = 0, x = pos.first, y = pos.second;
            // 周围八个位置的地雷数量
            for (int i = 0; i < 8; ++i) {
                int tx = x + dir_x[i];
                int ty = y + dir_y[i];
                if (tx < 0 || tx >= board.size() || ty < 0 || ty >= board[0].size()) {
                    continue;
                }
                // 不用判断 M，因为如果有 M 的话游戏已经结束了
                cnt += board[tx][ty] == 'M';
            }
            if (cnt > 0) {
                // 规则 3
                board[x][y] = char(cnt + '0');
            } else {
                // 规则 2
                board[x][y] = 'B';
                for (int i = 0; i < 8; ++i) {
                    int tx = x + dir_x[i];
                    int ty = y + dir_y[i];
                    // 这里不需要在存在 B 的时候继续扩展，因为 B 之前被点击的时候已经被扩展过了
                    if (tx < 0 || tx >= board.size() || ty < 0 || ty >= board[0].size() || board[tx][ty] != 'E' ||
                        vis[tx][ty]) {
                        continue;
                    }
                    // 找到未探索过的位置,加入队列
                    Q.push(make_pair(tx, ty));
                    vis[tx][ty] = true;
                }
            }
        }
    }

    vector<vector<char>> updateBoard(vector<vector<char>> &board, vector<int> &click) {
        int x = click[0], y = click[1];
        if (board[x][y] == 'M') {
            // 规则 1
            board[x][y] = 'X';
        } else {
            bfs(board, x, y);
        }
        return board;
    }
};
class Solution4 { // 题解 dfs
public:
    int dir_x[8] = {0, 1, 0, -1, 1, 1, -1, -1};
    int dir_y[8] = {1, 0, -1, 0, 1, -1, 1, -1};

    void dfs(vector<vector<char>>& board, int x, int y) {
        int cnt = 0;
        for (int i = 0; i < 8; ++i) {
            int tx = x + dir_x[i];
            int ty = y + dir_y[i];
            if (tx < 0 || tx >= board.size() || ty < 0 || ty >= board[0].size()) {
                continue;
            }
            // 不用判断 M，因为如果有 M 的话游戏已经结束了
            cnt += board[tx][ty] == 'M';
        }
        if (cnt > 0) {
            // 规则 3
            board[x][y] = char(cnt + '0');
        } else {
            // 规则 2
            board[x][y] = 'B';
            for (int i = 0; i < 8; ++i) {
                int tx = x + dir_x[i];
                int ty = y + dir_y[i];
                // 这里不需要在存在 B 的时候继续扩展，因为 B 之前被点击的时候已经被扩展过了
                if (tx < 0 || tx >= board.size() || ty < 0 || ty >= board[0].size() || board[tx][ty] != 'E') {
                    continue;
                }
                dfs(board, tx, ty);
            }
        }
    }

    vector<vector<char>> updateBoard(vector<vector<char>>& board, vector<int>& click) {
        int x = click[0], y = click[1];
        if (board[x][y] == 'M') {
            // 规则 1
            board[x][y] = 'X';
        } else {
            dfs(board, x, y);
        }
        return board;
    }
};



int main() {
    vector<vector<char>> board{{'E', 'E', 'E', 'E', 'E'},
                               {'E', 'E', 'M', 'E', 'E'},
                               {'E', 'E', 'E', 'E', 'E'},
                               {'E', 'E', 'E', 'E', 'E'}};
    vector<int> click{3, 0};
    Solution3 sol;
    auto ans = sol.updateBoard(board, click);
    for (auto &row:ans) {
        for (auto &col:row) {
            cout << col;
            cout << " ";
        }
        cout << endl;
    }
    return 0;
}